package com.zhu.solution.linkQuestion;


/*删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？
* */
/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/27/10:23
 * @Description:
 */
public class Solution_2 {

    public static void main(String[] args) {
        //输入的链表元素项，和要删除的节点
        int[] head = {1,2,3,4,5};
        int n = 5;

        //链表头节点
        ListNode headNode = new ListNode(head[0]);
        ListNode tempNode = headNode;
        //新建链表
        for (int i=1; i<head.length; i++){
            tempNode.next = new ListNode(head[i]);
            tempNode = tempNode.next;
        }

        //打印链表
        System.out.print("listNode");
        tempNode = headNode;
        while (tempNode != null){
            System.out.print(" --> " + tempNode.val);
            tempNode = tempNode.next;
        }

        //删除链表倒数 第n个节点
//        ListNode headTemp = new Solution_2().removeNthFromEnd(headNode,n);
//        ListNode headTemp = new Solution_2().removeNthFromEnd_2(headNode,n);
        ListNode headTemp = new Solution_2().removeNthFromEnd_3(headNode,n);

        System.out.println();
        //打印链表
        System.out.print("listNode");
        tempNode = headTemp;
        while (tempNode != null){
            System.out.print(" --> " + tempNode.val);
            tempNode = tempNode.next;
        }
    }

    /**
    * @Description: 删除链表倒数 第n个节点（自己）
    * @Param: [head, n]
    * @return: com.zhu.solution.linkQuestion.Solution_2.ListNode
    * @Author: zhujiabao
    * @Date: 2021/12/27
    */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //如果head节点为空，直接返回
        if (head == null || n == 0)
            return head;

        int length = 1;
        ListNode tempNode = head;
        //计算链表的长度
        while (tempNode.next!=null){
            tempNode = tempNode.next;
            length++;
        }
        //倒数第n个，就是正数第 length-n 个
        int temp = length - n;
        if (temp < 0)
            return head;
        else if (temp == 0)
            return head.next;
        else {
            tempNode = head;
            //找到到倒数第n+1个节点，下一个节点为倒数第n个节点
            while (temp>1){
                tempNode = tempNode.next;
                temp--;
            }
            tempNode.next = tempNode.next.next;
        }
        return head;
    }

    //双指针求解，（别人）
    public ListNode removeNthFromEnd_2(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;
        //fast移n步，
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //如果fast为空，表示删除的是头结点
        if (fast == null)
            return head.next;

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //这里最终slow不是倒数第n个节点，他是倒数第n+1个节点，
        //他的下一个结点是倒数第n个节点,所以删除的是他的下一个结点
        slow.next = slow.next.next;
        return head;
    }

    //递归求解
    public ListNode removeNthFromEnd_3(ListNode head, int n) {
        int pos = length(head, n);
        // 说明删除的是头节点
        if (pos == n)
            return head.next;
        return head;
    }
    // 获取节点所在位置，逆序
    public int length(ListNode node, int n) {
        if (node == null)
            return 0;
        int pos = length(node.next, n) + 1;
        //获取要删除链表的前一个结点，就可以完成链表的删除
        if (pos == n + 1)
            node.next = node.next.next;
        return pos;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}


